/*
 * Copyright (c) 2007, Nathan Sturtevant
 * All rights reserved.
 *
 * Redistribution and use in source and binary forms, with or without
 * modification, are permitted provided that the following conditions are met:
 *     * Redistributions of source code must retain the above copyright
 *       notice, this list of conditions and the following disclaimer.
 *     * Redistributions in binary form must reproduce the above copyright
 *       notice, this list of conditions and the following disclaimer in the
 *       documentation and/or other materials provided with the distribution.
 *     * Neither the name of the University of Alberta nor the
 *       names of its contributors may be used to endorse or promote products
 *       derived from this software without specific prior written permission.
 *
 * THIS SOFTWARE IS PROVIDED BY NATHAN STURTEVANT ``AS IS'' AND ANY
 * EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED
 * WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE
 * DISCLAIMED. IN NO EVENT SHALL <copyright holder> BE LIABLE FOR ANY
 * DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES
 * (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES;
 * LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND
 * ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
 * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF THIS
 * SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
 */
package com.googlecode.pathmachine.mm;

import java.util.ArrayDeque;
import java.util.ArrayList;
import java.util.List;
import java.util.Queue;
import java.util.logging.Logger;

/**
 * MinimalSectorAbstraction
 *
 * Builds a map abstraction
 *
 * Builds a map abstraction as described in AI Game Programming Wisdom 4.
 *
 * The abstraction is optimized to use relatively little memory.
 * This is the first version of the abstraction that I wrote.
 * The code could be a bit cleaner...but it works
 * 
 * @author Nathan Sturtevant
 * @author <a href="mailto:eriq.adams@gmail.com">Eriq Muhammad Adams J.</a>
 */
public class MinimalSectorAbstraction {

    private static final Logger logger = Logger.getLogger(MinimalSectorAbstraction.class.getName());
    public static final int MAX_NUM_PARENTS = 14;
    public static final int PARENT_BITS = 4;
    public static final int SECTOR_SIZE = 16;
    public static final int SECTOR_OFFSET_BITS = 4;
    public static final int MAX_NUM_EDGES = 7;
    private Map map;
    private int numXSectors;
    private int numYSectors;
    private List<SectorInfo> sectors;
    private List<Byte> memory;
    private List<List<Double>> regionError;
    private List<List<Integer>> areas;
    private int optimizationIndex;
    public static boolean DIAG_MOVES = true;
    private int sectorSize = SECTOR_SIZE;

    /**
     * MinimalSectorAbstraction()
     *
     * Constructor for minimal sector abstraction
     *
     * @param m The map for which the abstraction is created
     * @return none
     */
    public MinimalSectorAbstraction(Map map) {
        this.map = map;
        this.memory = new ArrayList<Byte>();
        numYSectors = ((map.getMapHeight() + sectorSize - 1) / sectorSize);
        numXSectors = ((map.getMapWidth() + sectorSize - 1) / sectorSize);
        int absSize = numXSectors * numYSectors;
        sectors = new ArrayList<SectorInfo>(absSize);
        for (int i = 0; i < absSize; i++) {
            sectors.add(new SectorInfo());
        }
        buildAbstraction();
        optimizationIndex = (int) sectors.size();
    }

    /**
     * getSector()
     *
     * Given an x/y coordinate, return the sector
     *
     * Given an x/y coordinate, return the sector
     *
     * @param x The x-coordinate for the computation
     * @param y The y-coordinate for the computation
     * @return The sector of the x/y coordinate
     */
    public int getSector(int x, int y) {
        if ((x < 0) || (y < 0)) {
            return -1;
        }
        int xsector = x / sectorSize;
        int ysector = y / sectorSize;
        if ((xsector >= numXSectors)
                || (ysector >= numYSectors)) {
            return -1;
        }
        return ysector * numXSectors + xsector;
    }

    /**
     * getRegion()
     *
     * Find the region associated with an x/y coordinate
     *
     * Returns the region of the sector that the x/y coordinate is in.
     * If coordinates are invalid, returns -1.
     *
     * @param x The x-coordinate for the computation
     * @param y The y-coordinate for the computation
     * @return The region for this coordinate
     */
    public int getRegion(int x, int y) {
        if (map.getTerrainType(x, y) != TTerrain.kGround) {
            return -1;
        }
        int sector = getSector(x, y);
        if (sectors.get(sector).numRegions == 1) // only one region, we must be in region 0
        {
            return 0;
        }

        List<Integer> regions = new ArrayList<Integer>();
        for (int i = 0; i < (sectors.get(sector).numRegions & 0xff); i++) {
            regions.add(0);
        }
        for (int t = 0; t < (sectors.get(sector).numRegions & 0xff); t++) {
            regions.set(t, (int) (memory.get(sectors.get(sector).memoryAddress + t * 2) & 0xff));
            //        printf("Region %d location %d\n", t, regions[t]);
        }
        return findParentRegion(x % sectorSize + ((y % sectorSize) * sectorSize), regions,
                x - x % sectorSize, y - y % sectorSize);
    }

    /**
     * getXYLocation()
     *
     * Given a sector and region, compute the x/y location.
     *
     * Given a sector and region, compute the x/y location.
     *
     * @param sector the sector to use
     * @param region the region to use
     * @return point2D of region center location
     */
    public Point2D getXYLocation(int sector, int region) {
        if (sectors.get(sector).numRegions == 0) {
            return null;
        }
        byte loc = memory.get(sectors.get(sector).memoryAddress + region * 2);
        int newloc = loc & 0xff;
        Point2D p = new Point2D();
        p.x = newloc % sectorSize;
        p.y = newloc / sectorSize;
        p.x += (sector % numXSectors) * sectorSize;
        p.y += (sector / numXSectors) * sectorSize;
        return p;
    }

    /**
     * getNeighbors()
     *
     * Find the edges in/out of the given sector
     *
     * Extract the edges from the abstraction and return them.
     *
     * @param sector The sector to use
     * @param region The region to use
     * @param edges On return contains the edges from this sector/region
     * @return none
     */
    public void getNeighbors(int sector, int region, List<TempEdgeData> edges) {

        int sectorAddress = sectors.get(sector).memoryAddress;
        int numRegions = sectors.get(sector).numRegions & 0xff;
        int numEdges, edgeStart;
        if (region == 0) {
            edgeStart = 0;
            numEdges = memory.get(sectorAddress + region * 2 + 1) & 0xff;
        } else {
            edgeStart = memory.get(sectorAddress + (region - 1) * 2 + 1) & 0xff;
            numEdges = memory.get(sectorAddress + region * 2 + 1) - edgeStart & 0xff;
        }
        for (int x = edgeStart; x < edgeStart + numEdges; x++) {
            TempEdgeData ted = new TempEdgeData();
            ted.from = region;
            if (DIAG_MOVES) {
                ted.direction = ((memory.get(sectorAddress + 2 * numRegions + x) & 0xff) >> 5) & 0x7;
                ted.to = (memory.get(sectorAddress + 2 * numRegions + x) & 0xff) & 0x1F;
            } else {
                ted.direction = ((memory.get(sectorAddress + 2 * numRegions + x) & 0xff) >> 6) & 0x3;
                ted.to = (memory.get(sectorAddress + 2 * numRegions + x) & 0xff) & 0x3F;
            }
            edges.add(ted);
        }
    }

    /**
     * getAdjacentSector()
     *
     * Returns the sector in a given direction
     *
     * Given a direction and a sector, compute which sector is immediately
     * adjacent in that direction.
     *
     * @param sector The sector to use
     * @param direction The direction to use
     * @return The sector in the particular direction
     */
    public int getAdjacentSector(int sector, int direction) {
        switch (direction) {
            case 0:
                return sector - numXSectors; // up
            case 1:
                return sector + 1; // right
            case 2:
                return sector + numXSectors; // down
            case 3:
                return sector - 1; // left
        }
        if (DIAG_MOVES) {
            switch (direction) {
                case 4:
                    return sector - numXSectors + 1; // up right
                case 5:
                    return sector + numXSectors + 1; // down right
                case 6:
                    return sector + numXSectors - 1;// down left
                case 7:
                    return sector - numXSectors - 1;// up left
            }
        }
        assert (false);
        return -1;
    }

    /**
     * optimizeRegionLocations()
     *
     * Perform complete optimization on map.
     *
     * @param none
     * @return none
     */
    public void optimizeRegionLocations() {
        initializeOptimization();
        while (!performOneOptimizationStep()) {
        }
    }

    /**
     * initializeOptimization()
     *
     * Initialize variables for optimization
     *
     * Optimization can be run in one step or incrementally. This initializes
     * the variables to run the optimization incrementally.
     *
     * @param none
     * @return none
     */
    public void initializeOptimization() {
        regionError = new ArrayList<List<Double>>(sectors.size());
        for (int i = 0; i < sectors.size(); i++) {
            regionError.add(new ArrayList<Double>());
        }
        optimizationIndex = 0;
    }

    /**
     * performOneOptimizationStep()
     *
     * Perform one optimization step. Must be called after InitializeOptimization().
     *
     * Perform a single optimization on the next sector to be optimized.
     *
     * @param none
     * @return true if the optimization is finished, false otherwise
     */
    public boolean performOneOptimizationStep() {
        if (optimizationIndex >= sectors.size()) {
            return true;
        }
        List<Double> re = regionError.get(optimizationIndex);
        for (int i = 0; i < (sectors.get(optimizationIndex).numRegions & 0xff); i++) {
            re.add(0.0);
        }
        for (int y = 0; y < (sectors.get(optimizationIndex).numRegions & 0xff); y++) {
            resetAbstractCenter(optimizationIndex, y);
            Point2D p = getXYLocation(optimizationIndex, y);
            int sx = p.x;
            int sy = p.y;
            getRegionError(optimizationIndex, y, sx, sy, sectorSize * 2 + 1);
            if (regionError.get(optimizationIndex).get(y) > sectorSize * 2) {
                moveRegionCenter(optimizationIndex, y);
            }
        }

        optimizationIndex++;
        return false;
    }

    /**
     * buildAbstraction()
     *
     * Start the abstraction buildling process.
     *
     * The abstraction is built in 3 steps. First, we identify the regions
     * in each sector. Then, we find the edges between each region.
     * Finally we store a compact representation of the abstraction.
     * An optimization phase can optionally be run.
     *
     * As this isn't production code, we don't actually free any of the
     * memory allocated during the construction of the abstraction.
     *
     * @param none
     * @return none
     */
    private void buildAbstraction() {
        int areasSize = numXSectors * numYSectors;
        areas = new ArrayList<List<Integer>>(areasSize);
        for (int i = 0; i < areasSize; i++) {
            areas.add(new ArrayList<Integer>());
        }
        for (int x = 0; x < numXSectors; x++) {
            for (int y = 0; y < numYSectors; y++) {
                int numRegions = getSectorRegions(areas.get(y * numXSectors + x), x, y);
                assert (numRegions < 256);
                sectors.get(y * numXSectors + x).numRegions = (byte) numRegions;
            }
        }

        for (int x = 0; x < numXSectors; x++) {
            for (int y = 0; y < numYSectors; y++) {
                List<TempEdgeData> edges = new ArrayList<TempEdgeData>();
                getEdges(areas, x, y, edges);
                assert (edges.size() < 256);
                sectors.get(y * numXSectors + x).numEdges = (byte) edges.size();
                storeSectorInMemory(sectors.get(y * numXSectors + x), areas.get(y * numXSectors + x), edges);
            }
        }

//        int nodes = 0, edges = 0;
//        for (int x = 0;
//                x < sectors.size(); x++) {
//            nodes += sectors.get(x).numRegions;
//            edges += sectors.get(x).numEdges;
//        }
//        logger.info(nodes + " regions and " + edges + " edges")
        optimizeRegionLocations();
        computePotentialMemorySavings();
    }

    /**
     * getEdges()
     *
     * Check for edges in and out of a sector.
     *
     * This is the high-level code which checks for edges between sectors
     *
     * \param areas An array which marks the region for each piece of the map
     * \param xSector The x-sector which we are checking
     * \param ySector The y-sector which we are checking
     * \param edges A vector of edge data holding the edges from this particular region
     * \return none
     */
    private void getEdges(List<List<Integer>> areas,
            int xSector, int ySector, List<TempEdgeData> edges) {
        boolean up = false, down = false, left = false, right = false;
        if (ySector > 0) // up
        {
            up = true;
            // get edge helper does the actual work of finding edges between adjacent sectors
            getEdgeHelper(areas.get(xSector + numXSectors * ySector), 0, 1,
                    areas.get(xSector + numXSectors * (ySector - 1)), sectorSize * (sectorSize - 1), 1,
                    edges, 0);
        }
        if (xSector > 0) // left
        {
            left = true;
            getEdgeHelper(areas.get(xSector + numXSectors * ySector), 0, sectorSize,
                    areas.get((xSector - 1) + numXSectors * ySector), sectorSize - 1, sectorSize,
                    edges, 3);
        }
        if (ySector < numYSectors - 1) // down
        {
            down = true;
            getEdgeHelper(areas.get(xSector + numXSectors * ySector), sectorSize * (sectorSize - 1), 1,
                    areas.get(xSector + numXSectors * (ySector + 1)), 0, 1,
                    edges, 2);
        }
        if (xSector < numXSectors - 1) // right
        {
            right = true;
            getEdgeHelper(areas.get(xSector + numXSectors * ySector), sectorSize - 1, sectorSize,
                    areas.get((xSector + 1) + numXSectors * ySector), 0, sectorSize,
                    edges, 1);
        }
        if (DIAG_MOVES) {
            // for diagonal moves, we directly check for diagonal moves -- all four points
            // on the corner of the sector must be free to allow an edge to be created.
            if (up && right) {
                if ((areas.get(xSector + numXSectors * (ySector)).get(sectorSize - 1) != -1) && // current
                        (areas.get(
                        xSector + numXSectors * (ySector - 1)).get(
                        sectorSize * sectorSize - 1) != -1) && // up
                        (areas.get(
                        xSector + 1 + numXSectors * (ySector - 1)).get(
                        sectorSize * (sectorSize - 1)) != -1) && // up right
                        (areas.get(
                        xSector + 1 + numXSectors * (ySector)).get(
                        0) != -1)) // right
                {
                    TempEdgeData ted = new TempEdgeData();
                    ted.from = areas.get(xSector + numXSectors * (ySector)).get(sectorSize - 1);
                    ted.to = areas.get(xSector + 1 + numXSectors * (ySector - 1)).get(sectorSize * (sectorSize - 1));
                    ted.direction = 4;
                    edges.add(ted);
                    //            printf("Adding diagonal edge between %d:(%d, %d) and %d:(%d, %d)\n",
                    //                         ted.from, xSector, ySector, ted.to, xSector+1, ySector-1);
                }
            }
            if (up && left) {
                if ((areas.get(xSector + numXSectors * (ySector)).get(0) != -1) && // current
                        (areas.get(xSector + numXSectors * (ySector - 1)).get(sectorSize * (sectorSize - 1)) != -1) && // up
                        (areas.get(xSector - 1 + numXSectors * (ySector - 1)).get(sectorSize * sectorSize - 1) != -1) && // up left
                        (areas.get(xSector - 1 + numXSectors * (ySector)).get(sectorSize - 1) != -1)) // left
                {
                    TempEdgeData ted = new TempEdgeData();
                    ted.from = areas.get(xSector + numXSectors * (ySector)).get(0);
                    ted.to = areas.get(xSector - 1 + numXSectors * (ySector - 1)).get(sectorSize * sectorSize - 1);
                    ted.direction = 7;
                    edges.add(ted);
                    //            printf("Adding diagonal edge between %d:(%d, %d) and %d:(%d, %d)\n",
                    //                         ted.from, xSector, ySector, ted.to, xSector-1, ySector-1);
                }
            }
            if (down && left) {
                if ((areas.get(xSector + numXSectors * (ySector)).get(sectorSize * (sectorSize - 1)) != -1) && // current
                        (areas.get(xSector + numXSectors * (ySector + 1)).get(0) != -1) && // down
                        (areas.get(xSector - 1 + numXSectors * (ySector + 1)).get(sectorSize - 1) != -1) && // down left
                        (areas.get(xSector - 1 + numXSectors * (ySector)).get(sectorSize * sectorSize - 1) != -1)) // left
                {
                    TempEdgeData ted = new TempEdgeData();
                    ted.from = areas.get(xSector + numXSectors * (ySector)).get(sectorSize * (sectorSize - 1));
                    ted.to = areas.get(xSector - 1 + numXSectors * (ySector + 1)).get(sectorSize - 1);
                    ted.direction = 6;
                    edges.add(ted);
                    //            printf("Adding diagonal edge between %d:(%d, %d) and %d:(%d, %d)\n",
                    //                         ted.from, xSector, ySector, ted.to, xSector-1, ySector+1);
                }
            }
            if (down && right) {
                if ((areas.get(xSector + numXSectors * (ySector)).get(sectorSize * sectorSize - 1) != -1) && // current
                        (areas.get(xSector + numXSectors * (ySector + 1)).get(sectorSize - 1) != -1) && // down
                        (areas.get(xSector + 1 + numXSectors * (ySector + 1)).get(0) != -1) && // down right
                        (areas.get(xSector + 1 + numXSectors * (ySector)).get(sectorSize * (sectorSize - 1)) != -1)) // right
                {
                    TempEdgeData ted = new TempEdgeData();
                    ted.from = areas.get(xSector + numXSectors * (ySector)).get(sectorSize * sectorSize - 1);
                    ted.to = areas.get(xSector + 1 + numXSectors * (ySector + 1)).get(0);
                    ted.direction = 5;
                    edges.add(ted);
                    //            printf("Adding diagonal edge between %d:(%d, %d) and %d:(%d, %d)\n",
                    //                         ted.from, xSector, ySector, ted.to, xSector+1, ySector+1);
                }
            }
        }
    }

    /**
     * getEdgeHelper()
     *
     * Generic procedure for iterating along the edge of a sector checking
     * for edges.
     *
     * GetEdgeHelper takes two (assumed) adjacent sectors and checks those sectors
     * for all edges between them. For each sector a startIndex and offset is used
     * so that the same code can be used for any two edges. Checks begin between
     * the startIndex and targetIndex and at each step the indices are updated by
     * the offset.
     *
     * @param startRegion This vector holds the region data for the starting sector
     * @param startIndex The first index to check in the startRegion
     * @param startOffset The offset (step) between indices we want to compare
     * @param targetRegion The region data for the goal sector
     * @param targetIndex The first index to check in the target region
     * @param targetOffset The offset (step) between indices we want to compare
     * @param edges The storage for any edges we find
     * @param direction The direction that all edges will go
     * @return none
     */
    private void getEdgeHelper(List<Integer> startRegion, int startIndex, int startOffset,
            List<Integer> targetRegion, int targetIndex, int targetOffset, List<TempEdgeData> edges, int direction) {
        int first = (int) edges.size();
        int last = -1;
        for (int x = 0; x < sectorSize; x++) {
            if ((startRegion.get(
                    startIndex) != -1)
                    && (targetRegion.get(targetIndex) != -1)) {
                if ((last == -1)
                        || (edges.get(edges.size() - 1).from != startRegion.get(startIndex))
                        || (edges.get(edges.size() - 1).to != targetRegion.get(targetIndex))) {
                    boolean here = false;
                    TempEdgeData ted = new TempEdgeData();
                    ted.from = startRegion.get(startIndex);
                    ted.to = targetRegion.get(targetIndex);
                    ted.direction = direction;
                    for (int y = first; y < edges.size(); y++) {
                        if (edges.get(y) == ted) {
                            here = true;
                            break;
                        }
                    }
                    if (!here) {
                        edges.add(ted);
                        last = (int) edges.size() - 1;
                    }
                }
            }
            startIndex += startOffset;
            targetIndex += targetOffset;
        }
    }

    /**
     * getSectorRegions()
     *
     * Do a BFS to find and label the regions in a sector
     *
     * Does a BFS to find and label all the regions in a sector.
     * Used when building the abstraction
     *
     * @param area Data structure containing the labelled points
     * @param absXSector The x offset of the sector
     * @param absYSector The y offset of the sector
     * @return The number of regions in the sector
     */
    private int getSectorRegions(List<Integer> area, int absXSector, int absYSector) {
        // initialize sector map to 0 for unsearched, -1 for unreachable
        for (int i = 0; i < sectorSize * sectorSize; i++) {
            area.add(0);
        }
        for (int x = 0; x < sectorSize; x++) {
            for (int y = 0; y < sectorSize; y++) {
                if (map.getTerrainType(absXSector * sectorSize + x,
                        absYSector * sectorSize + y) != TTerrain.kGround) {
                    area.set(y * sectorSize + x, -1);
                }
            }
        }

        int nextLabel = 1;
        for (int x = 0; x < sectorSize; x++) {
            for (int y = 0; y < sectorSize; y++) {
                if (area.get(y * sectorSize + x) == 0) {
                    labelRegion(area, x, y, nextLabel);
                    nextLabel++;
                }
            }
        }
        return nextLabel - 1;
    }

    /**
     * labelRegion()
     *
     * Do a BFS within a region to label it
     *
     * Performs the BFS within one region to label that region.
     *
     * @param area The stored labels
     * @param x The starting location for the BFS
     * @param y The starting location for the BFS
     * @param label The label to use
     * @return none
     */
    private void labelRegion(List<Integer> area, int x, int y, int label) {
        if ((y < 0) || (x < 0) || (y >= sectorSize) || (x >= sectorSize)) {
            return;
        }
        if (area.get(
                y * sectorSize + x) != 0) {
            return;
        }

        area.set(y * sectorSize + x, label);
        labelRegion(area, x + 1, y, label);
        labelRegion(area, x - 1, y, label);
        labelRegion(area, x, y + 1, label);
        labelRegion(area, x, y - 1, label);
    }

    /**
     * storeSectorInMemory()
     *
     * Store a sector and its edges/regions into the compressed data structure
     *
     * Store a sector into the compressed representation. Takes the edges
     * already computed and also computes the center of each region.
     *
     * @param si The data structure with the high-level sector information
     * @param area The region we are storing information for
     * @param edges a list of edges from this sector
     * @return none
     */
    private void storeSectorInMemory(SectorInfo si, List<Integer> area, List<TempEdgeData> edges) {
        // count number of edges for each region
        List<Integer> counts = new ArrayList<Integer>(si.numRegions & 0xff);
        for (int i = 0; i < (si.numRegions & 0xff); i++) {
            counts.add(0);
        }
        for (int y = 0; y < counts.size(); y++) {
            for (int x = 0; x < edges.size(); x++) {
                if (edges.get(
                        x).from == y + 1) {
                    counts.set(y, counts.get(y) + 1);
                }
            }
        }

        // now we know the size needed to store this, and
        // we can compute the rest of the abstraction info
        assert (memory.size() < (1 << 16));
        si.memoryAddress = (short) memory.size();
        int sum = 0;
        for (int x = 0; x < (si.numRegions & 0xff); x++) {
            sum += counts.get(x);
            // regions are numbered 0..n, but they are labelled 1..n+1
            // inside the area information
            memory.add(getAbstractLocation(area, x + 1));
            memory.add((byte) sum); // last edge of this parent

        }
        //    printf("Sum is %d, total is %d\n", sum, si.numEdges);
        assert (sum == (si.numEdges & 0xff));
        // Add all the edges;
        // this can be done faster, but I'm lazy
        for (int y = 0; y < counts.size(); y++) {
            for (int x = 0; x < edges.size(); x++) {
                if (edges.get(x).from == y + 1) {
                    memory.add(getAbstractEdge(edges.get(x)));
                }
            }
        }
    }

    /**
     * getAbstractEdge()
     *
     * Turn the edge data structure into a compressed edge.
     *
     * A quick helper function for turning tempEdgeData into a compressed (1byte)
     * edge representation.
     *
     * @param data edge data
     * @return A 1 byte representation of an edge
     */
    private byte getAbstractEdge(TempEdgeData data) {
        if (DIAG_MOVES) {
            return (byte) ((data.direction << 5) | ((data.to - 1) & 0x1F));
        } else {
            return (byte) ((data.direction << 6) | ((data.to - 1) & 0x3F));
        }
    }

    /**
     * getAbstractLocation()
     *
     * Choose a region center.
     *
     * Find a region center, placing it at the point closest to the
     * average weight of all points in the region.
     *
     * @param area The sector data for the computation
     * @param value The region number we are trying to analyze
     * @return The offset of the region center from the sector start
     */
    private byte getAbstractLocation(List<Integer> area, int value) {
        // find center of mass and get the point closest to it
        int xaverage = 0;
        int yaverage = 0;
        int count = 0;
        for (int x = 0; x < area.size(); x++) {
            if (area.get(
                    x) == value) {
                count++;
                xaverage += x % sectorSize;
                yaverage += x / sectorSize;
            }
        }
        xaverage /= count;
        yaverage /= count;
        int best = sectorSize * sectorSize;
        int index = -1;
        for (int x = 0; x < area.size(); x++) {
            if (area.get(x) == value) {
                int score = ((x % sectorSize) - xaverage) * ((x % sectorSize) - xaverage)
                        + (x / sectorSize - yaverage) * (x / sectorSize - yaverage);
                if (score < best) {
                    best = score;
                    index = x;
                }
            }
        }
        assert (index != -1);
        return (byte) index;
    }

    /**
     * findParentRegion()
     *
     * Helper function for GetRegion()
     *
     * Does a breadth-first search looking for the region associated with
     * a particular point.
     *
     * @param startLoc The initial offset in the region
     * @param parents The possible region centers
     * @param mapXOffset The x offset of the top of the sector
     * @param mapYOffset The y offset of the top of the sector
     * @return The region the point is in
     */
    private int findParentRegion(int startLoc, List<Integer> parents, int mapXOffset, int mapYOffset) {
        int current = startLoc;
        //Deque<Integer> stack = new ArrayDeque<Integer>();
        Queue<Integer> Q = new ArrayDeque<Integer>();
        List<Integer> markers = new ArrayList<Integer>();
        for (int i = 0; i < sectorSize * sectorSize; i++) {
            markers.add(0);
        }
        markers.set(current, 1);
        //    printf("Starting on %d\n", startLoc);
        boolean run = true;
        while (run) {
            for (int x = 0; x < parents.size(); x++) {
                if (current == parents.get(
                        x)) {
                    return (int) x;
                }
            }

            if ((current + sectorSize < sectorSize * sectorSize) && (markers.get(current + sectorSize) == 0)) {
                //stack.push_back(current+sectorSize);
                Q.add(current + sectorSize);
                markers.set(current + sectorSize, 1);
            }
            if ((current - sectorSize >= 0) && (markers.get(current - sectorSize) == 0)) {
                //stack.push_back(current-sectorSize);
                Q.add(current - sectorSize);
                markers.set(current - sectorSize, 1);
            }
            if ((((current + 1) % sectorSize) != 0) && (markers.get(current + 1) == 0)) {
                //stack.push_back(current+1);
                Q.add(current + 1);
                markers.set(current + 1, 1);
            }
            if (((current % sectorSize) != 0) && (markers.get(current - 1) == 0)) {
                //stack.push_back(current-1);
                Q.add(current - 1);
                markers.set(current - 1, 1);
            }

            do {
                //            printf("Stack size: %d\n", Q.size());
                assert (Q.size() != 0);
                current = Q.peek();
                Q.poll();
                //            printf("Checking %d next\n", current);
            } while ((markers.get(current) != 0)
                    && (map.getTerrainType(mapXOffset + current % sectorSize,
                    mapYOffset + current / sectorSize) != TTerrain.kGround));
        }
        return -1;
    }

    /**
     * getRegionError()
     *
     * Compute the "error" for the current region center
     *
     * Given a point within a region, compute the cost between that point
     * and every neighboring region. Use that cost to formulate an "error"
     * term which is returned.
     *
     * In this case we compuate the number of nodes expanded above what is
     * optimal (the optimal path length)
     *
     * An error bound is used to reduce computation. If this point is too expensive
     * (above the error limit) we can stop early.
     *
     * @param fromSector The sector we start in
     * @param fromRegion The region we start in
     * @param sx The start x-location in the region
     * @param sy The start y-location in the region
     * @param limit If the error exceeds this limit we can stop
     * @return none
     */
    private double getRegionError(int fromSector, int fromRegion, int sx, int sy, double limit) {
        GenericAStar gas = new GenericAStar();
        List<TempEdgeData> edges = new ArrayList<TempEdgeData>();
        getNeighbors(fromSector, fromRegion, edges);
        regionError.get(fromSector).set(fromRegion, 0.0);
        for (int z = 0; z < edges.size(); z++) {
            MapSearchEnvironment env = new MapSearchEnvironment(map);
            int toSector = getAdjacentSector(fromSector, edges.get(z).direction);
            int toRegion = edges.get(z).to;
            Point2D p = getXYLocation(toSector, toRegion);
            int gx = p.x, gy = p.y;
            List<Integer> thePath = new ArrayList<Integer>();
            // compute the cost to travel between the given sector/region and a neighboring region
            // We measure the cost as the number of nodes expanded over and above the optimal path
            // length
            gas.getPath(env, (gx << 16) | gy, (sx << 16) | sy, thePath);
            assert (!thePath.isEmpty());
            regionError.get(fromSector).set(fromRegion, max(regionError.get(fromSector).get(fromRegion),
                    gas.getNodesExpanded() - thePath.size()));
            if (FPUtil.fgreater(regionError.get(fromSector).get(fromRegion), limit)) {
                return regionError.get(fromSector).get(fromRegion);
            }

            // now do it again the other way, because we could go either way along this edge
            // and the costs can be highly assymetrical
            //thePath.resize(0);
            gas.getPath(env, (sx << 16) | sy, (gx << 16) | gy, thePath);
            assert (!thePath.isEmpty());
            regionError.get(fromSector).set(fromRegion, max(regionError.get(fromSector).get(fromRegion),
                    gas.getNodesExpanded() - thePath.size()));
            if (FPUtil.fgreater(regionError.get(fromSector).get(fromRegion), limit)) {
                return regionError.get(fromSector).get(fromRegion);
            }
        }
        return regionError.get(fromSector).get(fromRegion);
    }

    /**
     * moveRegionCenter()
     *
     * Optimize a region center
     *
     * Try every possible location for a region center. Choose the one
     * which minimizes the error returned by GetRegionError.
     *
     * @param sector The sector to test
     * @param region The region in the sector to test
     * @return none
     */
    public void moveRegionCenter(int sector, int region) {
        double error = regionError.get(sector).get(region);
        int best = -1;
        for (int x = 0; x < areas.get(sector).size(); x++) {
            if (areas.get(sector).get(x) == region + 1) {
                int xoff = (sector % numXSectors) * sectorSize;
                int yoff = (sector / numXSectors) * sectorSize;
                double err = getRegionError(sector, region, xoff + (x % sectorSize),
                        yoff + x / sectorSize, error);
                if (FPUtil.fless(err, error)) {
                    error = err;
                    best = x;
                }
            }
        }
        //printf("For %d:%d, error improved to %f at offset %d\n", sector, region, error, best);
        if (best != -1) {
            memory.set(sectors.get(sector).memoryAddress + 2 * region, (byte) best);
        }
    }

    /**
     * computePotentialMemorySavings()
     *
     * print how much memory would be saved using 'default' sectors
     *
     * print how much memory would be saved using 'default' sectors
     *
     * @param none
     * @return none
     */
    public void computePotentialMemorySavings() {
        int defaultSectors = 0;
        for (int x = 0;
                x < sectors.size(); x++) {
            //std::vector<sectorInfo> sectors;
            if (sectors.get(x).numRegions != 1) {
                continue;
            }

            if (sectors.get(x).numEdges != 8) {
                continue;
            }

            List<TempEdgeData> edges = new ArrayList<TempEdgeData>();
            List<Integer> edgedir = new ArrayList<Integer>(8);
            getNeighbors(x, 0, edges);
            for (int y = 0;
                    y < 8; y++) {
                edgedir.add(0);
            }
            for (int y = 0;
                    y < edges.size(); y++) {
                edgedir.set(edges.get(y).direction, 1);
            }

            // if there is one edge in each direction, this is a default sector
            int sum = 0;
            for (int y = 0;
                    y < edgedir.size(); y++) {
                sum += edgedir.get(y);
            }
            if (sum == 8) {
                defaultSectors++;
            }
        }
        //printf("%d default sectors would save %d bytes\n", defaultSectors, (8 + 2) * defaultSectors);
    }

    /**
     * resetAbstractCenter()
     *
     * Reset a region to the weighted average location.
     *
     * Resets a region center to the weighted average of the region. This is used
     * when optimizing an abstraction a second time to reset the location of the
     * abstract center.
     * 
     * Sometimes more than one region center will get moved to correct for some
     * topology feature, when only one region center really needs to be
     * moved. By moving the region center back to the default location we help
     * improve this case when running optimization a second time
     *
     * @param sector The sector to reset
     * @param region The region in the sector to reset
     * @return none
     */
    public void resetAbstractCenter(int sector, int region) {
        byte defaultCenter = getAbstractLocation(areas.get(sector), region + 1);
        memory.set(sectors.get(sector).memoryAddress + 2 * region, defaultCenter);
    }

    private double max(double a, double b) {
        return (((a) > (b)) ? (a) : (b));
    }

    public boolean compare(TempEdgeData x, TempEdgeData y) {
        return ((x.to == y.to)
                && (x.from == y.from)
                && (x.direction == y.direction));
    }

    /**
     * @return the numXSectors
     */
    public int getNumXSectors() {
        return numXSectors;
    }

    /**
     * @return the numYSectors
     */
    public int getNumYSectors() {
        return numYSectors;
    }

    /**
     * @return the sectorSize
     */
    public int getSectorSize() {
        return sectorSize;
    }

    /**
     * @return the map
     */
    public Map getMap() {
        return map;
    }

    /**
     * @return the sectors
     */
    public List<SectorInfo> getSectors() {
        return sectors;
    }
}
